package com.sheng.leetcode.year2025.month10.day06;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author by ls
 * @date 2025/10/14
 * <p>
 * 778. 水位上升的泳池中游泳<p>
 * <p>
 * 在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。<p>
 * 当开始下雨时，在时间为 t 时，水池中的水位为 t 。<p>
 * 你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。<p>
 * 假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。<p>
 * 你从坐标方格的左上平台 (0，0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间 。<p>
 * <p>
 * 示例 1:<p>
 * 输入: grid = [[0,2],[1,3]]<p>
 * 输出: 3<p>
 * 解释:<p>
 * 时间为0时，你位于坐标方格的位置为 (0, 0)。<p>
 * 此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。<p>
 * 等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你可以游向坐标方格中的任意位置<p>
 * <p>
 * 示例 2:<p>
 * 输入: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]<p>
 * 输出: 16<p>
 * 解释: 最终的路线用加粗进行了标记。<p>
 * 我们必须等到时间为 16，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的<p>
 * <p>
 * 提示:<p>
 * n == grid.length<p>
 * n == grid[i].length<p>
 * 1 <= n <= 50<p>
 * 0 <= grid[i][j] < n^2<p>
 * grid[i][j] 中每个值 均无重复<p>
 */
public class LeetCode0778 {

    @Test
    public void test01() {
        int[][] grid = new int[][]{{0, 2}, {1, 3}};
//        int[][] grid = new int[][]{{0, 1, 2, 3, 4}, {24, 23, 22, 21, 5}, {12, 13, 14, 15, 16}, {11, 17, 18, 19, 20}, {10, 9, 8, 7, 6}};
        System.out.println(new Solution().swimInWater(grid));
    }
}

class Solution {

    private static final int[][] DIRS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int[][] vis = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(vis[i], -1);
        }

        int left = Math.max(grid[0][0], grid[n - 1][n - 1]) - 1;
        int right = n * n - 1;
        // 开区间二分
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (dfs(0, 0, mid, grid, vis)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    // 判断在只访问 grid[i][j] <= mx 的情况下，能否到达终点
    private boolean dfs(int i, int j, int mx, int[][] grid, int[][] vis) {
        int n = grid.length;
        // 到达终点
        if (i == n - 1 && j == n - 1) {
            return true;
        }
        // 标记访问过，避免重复访问
        // 用 mx 区分不同时候的二分，如果 vis[x][y] != mx，说明不是本轮二分访问过的格子
        vis[i][j] = mx;
        // 访问相邻的格子
        for (int[] dir : DIRS) {
            int x = i + dir[0], y = j + dir[1];
            if (0 <= x && x < n && 0 <= y && y < n && grid[x][y] <= mx && vis[x][y] != mx) {
                if (dfs(x, y, mx, grid, vis)) {
                    return true;
                }
            }
        }
        return false;
    }
}
